<!DOCTYPE html>
<html>
<head>
<title>Leetcode和Acwing的每日一题好题积累</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<style type="text/css">
/* GitHub stylesheet for MarkdownPad (http://markdownpad.com) */
/* Author: Nicolas Hery - http://nicolashery.com */
/* Version: b13fe65ca28d2e568c6ed5d7f06581183df8f2ff */
/* Source: https://github.com/nicolahery/markdownpad-github */

/* RESET
=============================================================================*/

html, body, div, span, applet, object, iframe, h1, h2, h3, h4, h5, h6, p, blockquote, pre, a, abbr, acronym, address, big, cite, code, del, dfn, em, img, ins, kbd, q, s, samp, small, strike, strong, sub, sup, tt, var, b, u, i, center, dl, dt, dd, ol, ul, li, fieldset, form, label, legend, table, caption, tbody, tfoot, thead, tr, th, td, article, aside, canvas, details, embed, figure, figcaption, footer, header, hgroup, menu, nav, output, ruby, section, summary, time, mark, audio, video {
  margin: 0;
  padding: 0;
  border: 0;
}

/* BODY
=============================================================================*/

body {
  font-family: Helvetica, arial, freesans, clean, sans-serif;
  font-size: 14px;
  line-height: 1.6;
  color: #333;
  background-color: #fff;
  padding: 20px;
  max-width: 960px;
  margin: 0 auto;
}

body>*:first-child {
  margin-top: 0 !important;
}

body>*:last-child {
  margin-bottom: 0 !important;
}

/* BLOCKS
=============================================================================*/

p, blockquote, ul, ol, dl, table, pre {
  margin: 15px 0;
}

/* HEADERS
=============================================================================*/

h1, h2, h3, h4, h5, h6 {
  margin: 20px 0 10px;
  padding: 0;
  font-weight: bold;
  -webkit-font-smoothing: antialiased;
}

h1 tt, h1 code, h2 tt, h2 code, h3 tt, h3 code, h4 tt, h4 code, h5 tt, h5 code, h6 tt, h6 code {
  font-size: inherit;
}

h1 {
  font-size: 28px;
  color: #000;
}

h2 {
  font-size: 24px;
  border-bottom: 1px solid #ccc;
  color: #000;
}

h3 {
  font-size: 18px;
}

h4 {
  font-size: 16px;
}

h5 {
  font-size: 14px;
}

h6 {
  color: #777;
  font-size: 14px;
}

body>h2:first-child, body>h1:first-child, body>h1:first-child+h2, body>h3:first-child, body>h4:first-child, body>h5:first-child, body>h6:first-child {
  margin-top: 0;
  padding-top: 0;
}

a:first-child h1, a:first-child h2, a:first-child h3, a:first-child h4, a:first-child h5, a:first-child h6 {
  margin-top: 0;
  padding-top: 0;
}

h1+p, h2+p, h3+p, h4+p, h5+p, h6+p {
  margin-top: 10px;
}

/* LINKS
=============================================================================*/

a {
  color: #4183C4;
  text-decoration: none;
}

a:hover {
  text-decoration: underline;
}

/* LISTS
=============================================================================*/

ul, ol {
  padding-left: 30px;
}

ul li > :first-child, 
ol li > :first-child, 
ul li ul:first-of-type, 
ol li ol:first-of-type, 
ul li ol:first-of-type, 
ol li ul:first-of-type {
  margin-top: 0px;
}

ul ul, ul ol, ol ol, ol ul {
  margin-bottom: 0;
}

dl {
  padding: 0;
}

dl dt {
  font-size: 14px;
  font-weight: bold;
  font-style: italic;
  padding: 0;
  margin: 15px 0 5px;
}

dl dt:first-child {
  padding: 0;
}

dl dt>:first-child {
  margin-top: 0px;
}

dl dt>:last-child {
  margin-bottom: 0px;
}

dl dd {
  margin: 0 0 15px;
  padding: 0 15px;
}

dl dd>:first-child {
  margin-top: 0px;
}

dl dd>:last-child {
  margin-bottom: 0px;
}

/* CODE
=============================================================================*/

pre, code, tt {
  font-size: 12px;
  font-family: Consolas, "Liberation Mono", Courier, monospace;
}

code, tt {
  margin: 0 0px;
  padding: 0px 0px;
  white-space: nowrap;
  border: 1px solid #eaeaea;
  background-color: #f8f8f8;
  border-radius: 3px;
}

pre>code {
  margin: 0;
  padding: 0;
  white-space: pre;
  border: none;
  background: transparent;
}

pre {
  background-color: #f8f8f8;
  border: 1px solid #ccc;
  font-size: 13px;
  line-height: 19px;
  overflow: auto;
  padding: 6px 10px;
  border-radius: 3px;
}

pre code, pre tt {
  background-color: transparent;
  border: none;
}

kbd {
    -moz-border-bottom-colors: none;
    -moz-border-left-colors: none;
    -moz-border-right-colors: none;
    -moz-border-top-colors: none;
    background-color: #DDDDDD;
    background-image: linear-gradient(#F1F1F1, #DDDDDD);
    background-repeat: repeat-x;
    border-color: #DDDDDD #CCCCCC #CCCCCC #DDDDDD;
    border-image: none;
    border-radius: 2px 2px 2px 2px;
    border-style: solid;
    border-width: 1px;
    font-family: "Helvetica Neue",Helvetica,Arial,sans-serif;
    line-height: 10px;
    padding: 1px 4px;
}

/* QUOTES
=============================================================================*/

blockquote {
  border-left: 4px solid #DDD;
  padding: 0 15px;
  color: #777;
}

blockquote>:first-child {
  margin-top: 0px;
}

blockquote>:last-child {
  margin-bottom: 0px;
}

/* HORIZONTAL RULES
=============================================================================*/

hr {
  clear: both;
  margin: 15px 0;
  height: 0px;
  overflow: hidden;
  border: none;
  background: transparent;
  border-bottom: 4px solid #ddd;
  padding: 0;
}

/* TABLES
=============================================================================*/

table th {
  font-weight: bold;
}

table th, table td {
  border: 1px solid #ccc;
  padding: 6px 13px;
}

table tr {
  border-top: 1px solid #ccc;
  background-color: #fff;
}

table tr:nth-child(2n) {
  background-color: #f8f8f8;
}

/* IMAGES
=============================================================================*/

img {
  max-width: 100%
}
</style>
<script type="text/javascript">
document.addEventListener("DOMContentLoaded", function() {
    // 生成目录列表
    var toc = document.createElement("ul");
    toc.setAttribute("id", "table-of-content");
    toc.style.cssText = "border: 1px solid #ccc;";
    document.body.insertBefore(toc, document.body.childNodes[0]);
    // 用于计算当前标题层级的栈,先进先出,从左到右每一个元素代表当前标题所在的层级索引，初始为空
    var stack = new Array();
    // 获取所有标题
    var headers = document.querySelectorAll('h1,h2,h3,h4,h5,h6');
    for (var i = 0; i < headers.length; i++) {
        var header = headers[i];
        // 计算标题级数，为后面计算标号及缩进空格准备
        var level = parseInt(header.tagName.replace('H', ''), 10);
        // 通过两个where循环对栈进行调整,确保stack中标题级数与当前标题级数相同
        while(stack.length < level){
            stack.push(0);
        }
        while(stack.length > level){
            stack.pop();
        }
        // 最小一级标题标号步进+1
        stack[stack.length-1]++;
        // 生成标题标号( 1.1,1.2.. )
        var index = stack.join(".")
        // 生成标题ID
        var id = "title" + index;
        header.setAttribute("id", id);
        // 为标题加上标号,如果不希望显示标号，把下面这行注释就可以了
        header.textContent = index + " " + header.textContent;
        toc.appendChild(document.createElement("li"));
        var a = document.createElement("a");
        // 为目录项设置链接
        a.setAttribute("href", "#" + id)
        // 目录项文本前面放置缩进空格
        a.innerHTML = new Array(level * 4).join('&nbsp;') + header.textContent;
        toc.lastChild.appendChild(a);
    }
});
</script>
</head>
<body>
<h1>Leetcode和Acwing的好题</h1>
<h2>题目1：变位词组（7.18leetcode）</h2>
<p>链接：<a href="https://leetcode-cn.com/problems/group-anagrams-lcci/">https://leetcode-cn.com/problems/group-anagrams-lcci/</a></p>
<h3>题目叙述：</h3>
<p>编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。</p>
<p>注意：本题相对原题稍作修改</p>
<p>示例:</p>
<p>输入: [&quot;eat&quot;, &quot;tea&quot;, &quot;tan&quot;, &quot;ate&quot;, &quot;nat&quot;, &quot;bat&quot;],
输出:
[
  [&quot;ate&quot;,&quot;eat&quot;,&quot;tea&quot;],
  [&quot;nat&quot;,&quot;tan&quot;],
  [&quot;bat&quot;]
]
说明：</p>
<p>所有输入均为小写字母。
不考虑答案输出的顺序。</p>
<h3>思路</h3>
<p>字母相同而排序不同，则直接按升序排序后，完全相同，然后进行hash table计数（记住在未排序前的索引即可）</p>
<h3>个人cpp代码</h3>
<pre><code>class Solution {
public:
    vector&lt;vector&lt;string&gt;&gt; groupAnagrams(vector&lt;string&gt;&amp; strs) {
        vector&lt;string&gt;copy_strs = strs;
        int n=strs.size();
        int i;
        map&lt;string,vector&lt;int&gt;&gt; counter_map;
        vector&lt;int&gt;init_vector;
        for(i=0;i&lt;n;i++)
        {
            sort(strs[i].begin(),strs[i].end());
            //cout&lt;&lt;strs[i]&lt;&lt;endl;
            //cout&lt;&lt;(counter_map.find(strs[i])==counter_map.end())&lt;&lt;endl;
            if(counter_map.find(strs[i])==counter_map.end())
            {
                if(i!=0)init_vector.pop_back();
                init_vector.push_back(i);
                counter_map.insert(pair&lt;string,vector&lt;int&gt;&gt;(strs[i],init_vector));
            }
            else
            {
                counter_map[strs[i]].push_back(i);
            }
        }
        //cout&lt;&lt;counter_map[&quot;abt&quot;][0];
        vector&lt;vector&lt;string&gt;&gt;result_group;
        vector&lt;string&gt; strv1;
        for(map&lt;string,vector&lt;int&gt;&gt;::iterator it=counter_map.begin();it!=counter_map.end();it++)
        {
            for(int j=0;j&lt;it-&gt;second.size();j++)
            {
                int index;
                index = it-&gt;second[j];
                strv1.push_back(copy_strs[index]);
            }
            result_group.push_back(strv1);
            strv1.clear();
        }

    return result_group;
}
};
</code></pre>

<h2>题目2：检查是否区域内所有整数都被覆盖</h2>
<h3>题目描述：</h3>
<p>给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [starti, endi] 表示一个从 starti 到 endi 的 闭区间 。</p>
<p>如果闭区间 [left, right] 内每个整数都被 ranges 中 至少一个 区间覆盖，那么请你返回 true ，否则返回 false 。</p>
<p>已知区间 ranges[i] = [starti, endi] ，如果整数 x 满足 starti &lt;= x &lt;= endi ，那么我们称整数x 被覆盖了。</p>
<p> </p>
<p>示例 1：</p>
<p>输入：ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5</p>
<p>输出：true</p>
<p>解释：2 到 5 的每个整数都被覆盖了：</p>
<ul>
<li>2 被第一个区间覆盖。</li>
<li>3 和 4 被第二个区间覆盖。</li>
<li>5 被第三个区间覆盖。</li>
</ul>
<p><a href="https://leetcode-cn.com/problems/check-if-all-the-integers-in-a-range-are-covered/">https://leetcode-cn.com/problems/check-if-all-the-integers-in-a-range-are-covered/</a></p>
<h3>最优方法：差分数组</h3>
<h4>思路与算法</h4>
<p><img src="E:/笔记用图/上机笔记/3.png" /></p>
<h4>代码：</h4>
<pre><code>class Solution {
public:
    bool isCovered(vector&lt;vector&lt;int&gt;&gt;&amp; ranges, int left, int right) {
        vector&lt;int&gt; diff(52, 0);   // 差分数组
        for (auto&amp;&amp; range: ranges) {
            ++diff[range[0]];
            --diff[range[1]+1];
        }
        // 前缀和
        int curr = 0;
        for (int i = 1; i &lt;= 50; ++i) {
            curr += diff[i];
            if (i &gt;= left &amp;&amp; i &lt;= right &amp;&amp; curr &lt;= 0) {
                return false;
            }
        }
        return true;
    }
};
</code></pre>

<h4>复杂度分析</h4>
<p>复杂度分析：（注意，这里面都是l 不是1！）</p>
<p>时间复杂度：O(n+l)，其中 n 为ranges 的长度，l 为 diff 的长度。初始化 diff 数组的时间复杂度为 O(l)，遍历 ranges 更新差分数组的时间复杂度为 O(n)，求解前缀和并判断是否完全覆盖的时间复杂度为 O(l)。</p>
<p>空间复杂度：O(l)，即为 diff 的长度。</p>
<h3>方法2（个人方法） 区间左端点排序</h3>
<h4>思路</h4>
<p>对区间按左端点排序。</p>
<p>排序后遍历ranges，判断left第一次落在li，right第一次落在ri。</p>
<p>然后，从li遍历到ri，要求：</p>
<p>每次记录下最右边的位置 mostright</p>
<p>如果下一个的左端点位置 比最右位置mostright 大了 2或者更多，则说明找不到，否则则可以找到</p>
<h4>代码</h4>
<pre><code>class Solution {
public:
    bool isCovered(vector&lt;vector&lt;int&gt;&gt;&amp; ranges, int left, int right) {
        function &lt;bool(vector&lt;int&gt;,vector&lt;int&gt;)&gt; left_sort = [&amp;] (vector&lt;int&gt; x,vector&lt;int&gt; y)
        {
            if(x[0]&lt;y[0])return true;
            return false;
        };

        sort(ranges.begin(),ranges.end(),left_sort);
        int n=ranges.size();
        int i;
        int li=-1;
        int ri=-1;
        for(i=0;i&lt;n;i++)
        {
            for(int j=0;j&lt;=1;j++)
                cout&lt;&lt;ranges[i][j]&lt;&lt;&quot; &quot;;
            cout&lt;&lt;endl;
        }
        for(i=0;i&lt;n;i++)
        {
            if(left&gt;=ranges[i][0] and left&lt;=ranges[i][1])
            {
                li=i;
                break;
            }
        }
        for(i=0;i&lt;n;i++)
        {
            if(right&gt;=ranges[i][0] and right&lt;=ranges[i][1])
            {
                ri=i;
                break;
            }
        }
        cout&lt;&lt;li&lt;&lt;&quot;;&quot;&lt;&lt;ri&lt;&lt;endl;
        if(li==-1 or ri==-1)return false;
        if(li==ri)return true;
        int most_right=0;
        for(i=li;i&lt;ri;i++)
        {
            if(ranges[i][1]&gt;most_right)most_right=ranges[i][1];
            if(ranges[i+1][0]-most_right&gt;1)return false;
        }
        return true;
    }
};
</code></pre>


</body>
</html>
<!-- This document was created with MarkdownPad, the Markdown editor for Windows (http://markdownpad.com) -->
